package graph.base;

import linear.Stack;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 基于深度搜索路径
 */
public class DepthFirstPaths {
    private boolean[] marked;
    // 起点
    private int s;
    // 索引表示起点 值表示s到当前顶点路径的最后一个顶点
    private int[] edgeTo;

    public DepthFirstPaths(Graph g, int s) {
        this.s = s;
        this.marked = new boolean[g.V()];
        this.edgeTo = new int[g.V()];
        dfs(g, s);
    }

    private void dfs(Graph G, int v) {
        marked[v] = true;
        for (Integer i : G.adj(v)) {
            if (!marked[i]) {
                edgeTo[i] = v;
                dfs(G, i);
            }
        }


    }

    public Stack<Integer> pathTo(int v) {
        if (!hasPathTo(v)) {
            return null;
        }
        Stack<Integer> result = new Stack<>();
        for (int i = v; i != s; i = edgeTo[i]) {
            result.push(i);
        }
        // 起点
        result.push(s);
        return result;
    }

    public boolean hasPathTo(int v) {
        return marked[v];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(
                        DepthFirstSearch.class.getClassLoader().getResourceAsStream("road_find.txt")));
        // 读取城市数目，初始化Graph图
        int number = Integer.parseInt(reader.readLine());
        Graph G = new Graph(number);
        // 读取城市的连通道路
        int roadNumber = Integer.parseInt(reader.readLine());
        // 循环读取道路，并调用addEdge方法
        for (int i = 0; i < roadNumber; i++) {
            String line = reader.readLine();
            int p = Integer.parseInt(line.split(" ")[0]);
            int q = Integer.parseInt(line.split(" ")[1]);
            G.addEdge(p, q);
        }
        // 根据图G和顶点0路径查找对象
        DepthFirstPaths paths = new DepthFirstPaths(G, 0);
        // 获取0到4的路径
        Stack<Integer> path = paths.pathTo(4);
        //遍历打印
        StringBuilder sb = new StringBuilder();
        for (Integer v : path) {
            sb.append(v).append("-");
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb);
    }
}
